//
// Description: 581. 最短无序连续子数组
// Created by Loading on 2021/8/3.
//

#include <bits/stdc++.h>

using namespace std;

int findUnsortedSubarray(vector<int> &nums) {
    // 已经是有序的
    if (is_sorted(nums.begin(), nums.end())) {
        return 0;
    }
    vector<int> sort_nums = nums;
    sort(sort_nums.begin(), sort_nums.end());
    // 寻找无序的起始点
    int left = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != sort_nums[i]) {
            left = i;
            break;
        }
    }
    // 寻找无序的结尾点
    int right = (int) nums.size() - 1;
    for (int i = (int) nums.size() - 1; i >= 0; --i) {
        if (nums[i] != sort_nums[i]) {
            right = i;
            break;
        }
    }

    return right - left + 1;
}

// 一次遍历
int findUnsortedSubarray2(vector<int> &nums) {
    int n = nums.size();
    int maxn = INT_MIN, right = -1;
    int minn = INT_MAX, left = -1;
    // 找到无序的左端点和右端点
    for (int i = 0; i < n; i++) {
        if (maxn > nums[i]) {
            right = i;
        } else {
            maxn = nums[i];
        }
        if (minn < nums[n - i - 1]) {
            left = n - i - 1;
        } else {
            minn = nums[n - i - 1];
        }
    }
    // right == -1 或 left == -1 说明数组原本有序
    return right == -1 ? 0 : right - left + 1;
}

int main() {
    vector<int> nums = {2, 6, 4, 8, 10, 9, 15};
    cout << findUnsortedSubarray(nums) << endl;
    cout << findUnsortedSubarray2(nums) << endl;
}